package graduation.project.body;

import graduation.project.exception.NonExpressionException;
import graduation.project.utilities.Utility;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Note: when the number of variables in expression is equal or larger than 32,
 * the program will break.
 * 
 * @author robin
 * 
 */
public class Expression {

	// private final String ID;
	protected final String expression;
	protected final String dnf;
	protected String model;

	/***************************************************************************
	 * if expression is "", expression is invalid.
	 * 
	 * @param expression
	 * @throws NonExpressionException
	 */
	public Expression(String expression) throws NonExpressionException {

		expression = expression.replaceAll("\\s", "");
		if (!Utility.checkExpressionValid(expression))
			throw new NonExpressionException();

		this.expression = expression;
		this.dnf = toDNF(expression);
		this.model = generateModel(dnf);
		// this.ID = dnf + new RandomNum().generateNum();
	}

	/*
	 * public String getID(){ return ID; }
	 */
	public String getDNF() {
		return dnf;
	}

	public String getExpression() {
		return expression;
	}

	public String getModel() {
		if (model == null || model.equals(""))
			return generateModel(dnf);
		return model;
	}

	/**
	 * should add some preparation: delete the terms in the both expression.
	 */
	public boolean equals(Object expr) {

		if (!(expr instanceof Expression))
			return false;
		if (expr == null)
			return false;

		Expression exp = (Expression) expr;
		String mo = exp.getModel();

		if (expression.equals(exp.getExpression())
				|| expression.equals(exp.getDNF()))
			return true;
		if (model.length() != mo.length())
			return false;
		for (int i = 0; i < model.length(); i++)
			if (mo.indexOf(model.charAt(i)) < 0)
				return false;

		for (int i = 0; i < (int) Math.pow(2.0, model.length()); i++)
			if (evaluate(i, model) != exp.evaluate(i, model))
				return false;

		return true;
	}

	public String toString() {
		return "Expression: " + expression + ", DNF form: " + dnf;
	}

	/**
	 * 
	 * 
	 * @param testDate
	 * @param model
	 * @return
	 */
	public boolean evaluate(int testData, String model) {
		int[] intArr = testDataToIntArray(testData, model.length());
		return evaluate(getDNF(), intArr, model);
	}

	public boolean evaluate(int[] testData, String model) {
		String expression = getDNF();
		return evaluate(expression, testData, model);
	}

	public boolean evaluate(String expression, int testData, String model) {
		int[] intArr = testDataToIntArray(testData, model.length());
		return evaluate(expression, intArr, model);
	}

	public boolean evaluate(String expression, int[] testData, String model) {
		String[] terms = expression.split("\\+");
		for (int i = 0; i < terms.length; i++) {
			if (isTermTrue(terms[i], testData, model))
				return true;
		}
		return false;
	}

	/**
	 * Given a term and test Data, evaluate the term is true or false.
	 * 
	 * @param term
	 * @param testData
	 * @param model
	 * @return
	 */
	public static boolean isTermTrue(String term, int testData, String model) {
		int[] intArr = testDataToIntArray(testData, model.length());
		return isTermTrue(term, intArr, model);
	}

	public static boolean isTermTrue(String term, int[] testData, String model) {
		int result = 1;

		char ch;
		for (int i = 0; i < term.length(); i++) {
			ch = term.charAt(i);
			if (ch == '!') {
				// fix
				if (i + 1 < term.length()) {
					i++;
//					System.out.println(term.charAt(i));
				} else {
					//
					System.out.println("else");
				}
				ch = term.charAt(i);
				result = result * (testData[model.indexOf(ch)] * -1 + 1);
			} else
				result = result * testData[model.indexOf(ch)];

			if (result == 0)
				return false;
		}

		return true;
	}

	public static int[] testDataToIntArray(int testData, int size) {
		String binaryString = Integer.toBinaryString(testData);
		int[] intArr = new int[size];
		for (int i = intArr.length - 1, j = binaryString.length() - 1; i >= 0
				&& j >= 0; i--, j--) {
			intArr[i] = Integer.parseInt("" + binaryString.charAt(j));
		}
		return intArr;
	}

	/**
	 * Here to generate a dnf expression, call this function must check the
	 * input parameter valid, and get rid of all whitespace. the most
	 * complicated expression like: ... +abc(...)bd(abc+...+ed(....)cd + ac)ed
	 * +...
	 * 
	 * @param expression
	 * @return
	 */
	public String toDNF(String exp) {

		String originEx = exp;
		Pattern p = Pattern.compile("[^+()]*(\\([^()]*\\)[^()+]*)+");
		Map<String, String> map = new HashMap<String, String>();
		Set<String> keys;

		StringBuffer origin = new StringBuffer();
		origin.append(originEx);
		while (true) {
			if (!(Pattern.matches(".*[^+()]*(\\([^()]*\\)[^()+]*)+.*", origin)))
				break;
			Matcher m = p.matcher(origin);
			while (m.find()) {
				String key = m.group();
				String value = offBracket(key);
				map.put(key, value);
			}
			keys = map.keySet();
			Iterator<String> it = keys.iterator();
			while (it.hasNext()) {
				String key = (String) it.next();
				String value = (String) map.get(key);
				int begin = origin.indexOf(key);
				if (((begin + key.length() < origin.length()) && origin
						.charAt(begin + key.length()) == '(')
						|| ((begin > 0) && origin.charAt(begin - 1) == ')'))
					value = "(" + value + ")";
				origin.replace(origin.indexOf(key), origin.indexOf(key)
						+ key.length(), value);
			}
			map.clear();
			keys.clear();
		}
		originEx = origin.toString();
		originEx = originEx.replaceAll("\\++", "+");

		if (originEx.length() != 0 && originEx.charAt(0) == '+')
			originEx = originEx.replace("+", "");
		if (originEx.length() != 0
				&& originEx.charAt(originEx.length() - 1) == '+')
			originEx = originEx.substring(0, originEx.length() - 1);

		return originEx;
	}

	/**
	 * toDNF() method will call this method. deal with the simple expression
	 * with one parentheses.
	 * 
	 * get rid of the parentheses, the originEx is like "abc(ef + !gh)d", abc(sd
	 * +ds), abc(ac + ed)(kj + ij)er.
	 * 
	 * @param originEx
	 * @return
	 */
	private String offBracket(String originEx) {

		StringBuffer result = new StringBuffer();
		StringBuffer origin = new StringBuffer();
		origin.append(originEx);
		Pattern p = Pattern.compile("!\\([^()]*\\)");
		Matcher m = p.matcher(originEx);
		String subString;
		while (m.find()) {
			subString = m.group();
			origin.replace(origin.indexOf(subString), origin.indexOf(subString)
					+ subString.length(), notOperation(subString));
		}
		// System.out.println("offBracket, origin: " + origin.toString());

		result.append(origin.subSequence(0, origin.indexOf("(")));
		origin.delete(0, origin.indexOf("("));

		while (true) {
			int begin = origin.indexOf("(");
			int end = origin.indexOf(")") + 1;
			String in;
			if (begin < 0) {
				if (origin.toString().equals(""))
					break;
				else {
					begin = 0;
					end = origin.length();
					in = "(" + origin.substring(begin, end) + ")";
				}
			} else if (begin != 0) {
				end = begin;
				begin = 0;
				in = "(" + origin.substring(begin, end) + ")";
			} else
				in = origin.substring(begin, end);

			String[] outTerms = result.toString().split("\\+");

			origin.delete(begin, end);
			result.delete(0, result.length());

			for (int i = 0; i < outTerms.length; i++) {
				String temp = simpleOffBracket(outTerms[i] + in);
				if (!(temp.trim().equals(""))) {
					result.append(temp).append('+');
				}
			}
			if (result.length() != 0
					&& result.charAt(result.length() - 1) == '+')// delete
																	// the last
																	// redundant
																	// "+" sign.
				result.deleteCharAt(result.length() - 1);
			// result.delete(result.length() - 1, result.length());
			if (origin.length() == 0) // modify the variable result to origin,
										// need consideration
				break;
		}
		return result.toString();
	}

	/***************************************************************************
	 * called by offBracket(), deal with the expression like: !(abc), !(ab +
	 * cd), such as.
	 * 
	 * @param originEx
	 * @return
	 */
	private String notOperation(String originEx) {
		StringBuffer result = new StringBuffer();

		String inTerm;
		String[] inTerms = originEx.substring(2, originEx.length() - 1).split(
				"\\+");//

		for (int i = 0; i < inTerms.length; i++) {
			result.append('(');
			inTerm = inTerms[i];
			for (int j = 0; j < inTerm.length(); j++) {
				if (inTerm.charAt(j) == '!') {
					j++;
					result.append(inTerm.charAt(j)).append('+');
				} else
					result.append('!').append(inTerm.charAt(j)).append('+');
			}
			result.delete(result.length() - 1, result.length());// result.deleteCharAt(result.length()-1);
			result.append(')');
		}
		return result.toString();
	}

	/**
	 * calld by offBracket() method; function: get rid of the parentheses, like
	 * abc(ef + gh), abc(!ef + gh), the simplest format.
	 * 
	 * @param originEx
	 * @return
	 */
	private String simpleOffBracket(String originEx) {
		String out = originEx.substring(0, originEx.indexOf('('));
		String in = originEx.substring(originEx.indexOf('(') + 1, originEx
				.indexOf(')'));
		StringBuffer result = new StringBuffer();

		String[] innerTerms = in.split("\\+");
		for (int i = 0; i < innerTerms.length; i++) {
			String temp = termMultiple(out, innerTerms[i]);
			if (!(temp.equals("")))
				result.append(temp).append('+');
		}

		if (result.length() != 0 && result.charAt(result.length() - 1) == '+')
			result.deleteCharAt(result.length() - 1);
		// result.delete(result.length() - 1, result.length());// get rid of the
		// last redundant '+' sign.
		return result.toString();
	}

	/**
	 * used to calculate a term multiple another term, like (abcd)(!abcefg).
	 * Here don't consider not invalid expression
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	private String termMultiple(String s1, String s2) {
		StringBuffer result = new StringBuffer();

		char ch; // used to store temporary character
		int pos;

		s1 = s1.concat(s2); // the simplest result
		// check the result invalid, and get rid of redundant
		for (int i = 0; i < s1.length(); i++) {
			ch = s1.charAt(i);
			if (ch == '!') {
				i++;
				ch = s1.charAt(i);
				pos = result.indexOf("" + ch);
				if (pos < 0)
					result.append('!').append(ch);
				else if (pos == 0 || result.charAt(pos - 1) != '!')
					return "";
			} else {
				pos = result.indexOf("" + ch);
				if (pos < 0)
					result.append(ch);
				else if (pos != 0 && result.charAt(pos - 1) == '!')
					return "";
			}
		}
		return result.toString();
	}

	/**
	 * Given a boolean expression, derive the corresponding variables.
	 * 
	 * @param exp
	 * @return
	 */
	public String generateModel(String exp) {

		exp = exp.replaceAll("\\s|\\(|\\)|\\!|\\+", "");
		StringBuffer model = new StringBuffer();
		char ch;

		for (int i = 0; i < exp.length(); i++) {
			ch = exp.charAt(i);
			if (model.indexOf("" + ch) < 0)
				model.append(ch);
		}
		return model.toString();
	}

	public static void main(String[] args) throws NonExpressionException {

		/*
		 * Expression ex = new Expression("(a(!d + !e + de!(!fgh!i +
		 * !ghi)!(!fglk + !g!ik)) + !(!fgh!i + !ghi)!(!fglk + !g!ik)(b + c!m +
		 * f))(a!b!c + !ab!c + !a!bc)"); System.out.println("DNF: " +
		 * ex.getDNF());
		 * 
		 * int[] test = Expression.testDataToIntArray(1, 2); for(int i = 0; i <
		 * test.length; i++) System.out.println("i" + test[i]);
		 */

		OriginExpression originEx = new OriginExpression("!(ab!cd)");
		int[][] hdAr = OriginExpression.getAllHDArray(originEx);
		if (hdAr == null)
			System.out
					.println("the expression doesnot have cells with HD = -p.");
		else
			for (int i = 0; i < hdAr.length; i++) {
				System.out.print("i=" + i + ": ");
				for (int j = 0; j < hdAr[i].length; j++)
					System.out.print(hdAr[i][j] + ", ");
				System.out.println("");
			}

	}
}
